#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const int N = 2e5 + 10;
#define INF 0x3f3f3f3f;
typedef long long int ll;
#define close(); std::ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
//----------------------------------------------------------------------------//
int n, m;
void solve()
{
    string s;
    cin >> n >> m >> s;

    map<char, int> cnt;

    for(int i = 0; i < n; i++) cnt[s[i]]++;

    int ans = 0;
    for(auto[k, v] : cnt)
    {
        if(v == 0) continue;

        char cur = k;
        if(cur > 'a')//大写字母
        {
            ans += min(cnt[cur], cnt[cur - 32]);
            int calc = v;
            int calc2 = cnt[cur - 32];
            cnt[cur] -= min(calc, calc2);
            cnt[cur - 32] -= min(calc, calc2);
        }
        else//小写字母
        {
            ans += min(cnt[cur], cnt[cur + 32]);
            int calc = v;
            int calc2 = cnt[cur + 32];
            cnt[cur] -= min(calc, calc2);
            cnt[cur + 32] -= min(calc, calc2);
        }
    }

    int x = 0;
    for(auto[k, v] : cnt)
    {
        int calc = v;
        x += calc / 2;
    }

    cout << ans + min(m, x) << '\n';//每次操作消费一次m,看m和x谁小


}

int main()
{
    close();
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}